1. Field of the Invention
The present invention relates generally to image processing systems and, more particularly, to systems for recognizing graphical objects in drawings, such as for generating drawing databases.
2. Description of the Related Art
A conventional system for recognizing graphical objects in a drawing is discussed in "Interactive Drawing Input System," Nikkei CG, pages 120-130, April 1987, which is hereby incorporated by reference. This system relies on a line tracking recognition strategy.
The configuration of this conventional system is shown in FIG. 1. The drawing recognition system comprises an image reader 11, a video display 12, an input device 13, a data processing system 14, having a memory 14a and a processor 14b, and a drawing plotter 15. The data processing system 14 executes a drawing recognition program 65 for recognizing graphical objects in an image that has been read by the image reader 11. The major components of the drawing recognition program 65 are shown in FIG. 2. The drawing recognition program 14 comprises a tracking start point determination program 66, a line tracking program 67, and a tracking candidate determination program 68.
The operation of the conventional system will now be described with reference to an example shown in FIGS. 3a-3d. First, a drawing is digitized by the image reader 11 to produce digital image data, and the data is fed to the data processing system 14. In this context, a "drawing" is any printed image on a suitable physical medium, such as paper. Digital image data is represented as an x-y coordinate grid of pixels represented by binary values. The digital image data is then displayed on the video display 12 so that an operator may view the image that has been read.
The operator then uses the input device 13, which may be a mouse or tablet, to designate a type of a chart to be recognized, by selecting the type from a pre-programmed menu list. For example, the list may include a number of patterns which may be recognized such as polygons, lines of different thicknesses, circles and arcs, etc.
Examples of types of charts to be recognized are shown in FIG. 23a-23d. A simple chart (FIG. 23a) is a line of constant width and indefinite length, which may be solid, broken or a chain. In an equipment drawing, a simple chart may represent an electrical power line, for example.
A compound chart is a combination of simple charts, which in an equipment drawing may represent equipment. Three examples are shown in FIG. 23b.
A graphic pattern is a pattern illustrating configurations of objects. On a map, a graphic pattern may represent roads and houses (see FIG. 23c).
Symbols are marks of constant size which indicate specific objects. On a map a symbol may represent, for example, a school or post office. On equipment drawings it may represent, for example, an electric power pole (see FIG. 23d). In the present example, assume that the operator selects a "polygon" with the input device 13 (FIG. 1) as the type of chart to be recognized.
Having specified the chart type, the operator specifies a tracking start point Q, for the graphical object 70 (FIG. 3a) to be recognized, in response to a tracking start position determination program 66 (FIG. 2). The position Q is identified by using the input device 13 (FIG. 1) to move a cursor on the video display 12 to the desired position on the displayed image. Point Q, known as the tracking start position, is the point at which tracking of the graphical object 70 begins.
Often, the point Q designated by an operator is not located on the chart to be recognized. Thus, the tracking start position determination program prompts the user to select another point Q on the chart until the actual selected point Q is on the chart. In this and other CAD systems, the requirement that a designated point Q must be on a line in the image results in fatigue and annoyance of the operator.
Once the tracking start position Q is designated, a line tracking program 67 (FIG. 2) is executed to begin tracking a line in any direction on the object 70 (FIG. 3a) from the tracking start point Q.
Tracking of a line is performed on the basis that, for each line, a function can be determined to define the line in terms of y=ax+b, where a is the slope of the line and b is an offset. Also, a thickness can be determined. Similarly, the radius of curvature defines arcs and circles. Tracking of a line is performed by incrementing x, determining y, and determining if image data is found at the newly determined x,y coordinates, with the desired line thickness. When there is no more data in a given direction, tracking in that direction stops, and a new direction is determined.
In the example of FIG. 3a, the tracking progresses in the direction of the arrow X (FIG. 3a) as indicated by the shaded region 72 in FIG. 3b. When branch point T is reached, tracking continues in the same direction, as it is possible to continue. At the corner C, the direction of tracking is changed. When branch point K is reached (FIG. 3C), a decision must be made as to whether tracking should continue in direction "R" or whether alternatively to proceed along line "S". This determination is made by the operator based upon the type of graphical object that is to be recognized. That is, the shape of the object to be recognized can suggest the proper changes in tracking direction. In this instance, branching should be carried out nearly orthogonally. That is, tracking should continue in the rectilinear direction, the direction "R", in which the tracking of the object 70 is optimized.
When it is not clear which tracking direction should be selected, a tracking candidate determination program 68 (FIG. 2) presents multiple tracking candidates to the operator in descending order of probability and requests the operator to designate a candidate. In FIG. 3c, tracking directions R and S are presented as candidates. In response to these candidates, the operator manipulates the input device 13 (FIG. 1) to select the correct tracking direction R. Then, the line tracking program 67 (FIG. 2) resumes tracking.
When the line tracking program 67 (FIG. 2) completes tracking a line of an intended graphic (i.e., the tracking is completed around the graphical 70), the system has a complete recognized graphical object. In the example case at FIG. 3d, the tracking has returned to the tracking start point Q. For objects which are not closed, tracking terminates when the object has been recognized or when no more image data remains to be traced. At this point, the system recognizes that the graphical object 70 is a "polygon" and tracking is terminated.
The above described steps are repeated for each of the graphical objects in the drawing. The steps are repeated until all of the graphical objects have been recognized.
In order to recognize a chart in a drawing containing overlapping graphics, an operator of the conventional system must designate which line is tracked at every point at which the currently tracked line overlaps another graphic and the direction of tracking needs to be changed. Thus, the operator is forced to carry out a number of complicated operations. Furthermore, if a drawing contains a dashed line or a dot-dash line which overlaps another graphic or has deteriorated due to frequent copying so that lines discontinue or blur, a conventional drawing recognition system fails to track a line and extract an object graphic. Likewise, when a graphical object is made of multiple charts (hereafter referred to as a "compound chart") each line must be designated in order for the compound chart to be recognized. This increases an operator's work load and may also result in the failure to track a line due to a discontinuation in the line.
Moreover, when symbols are appended to a chart or a compound chart, the operator must designate the chart and symbols separately. When the drawing contains isolated symbols or a row of characters exist in an area where various graphic elements are arranged densely, entry of such isolated symbols or text string requires the operator to designate positions, inclinations and types of such symbols or characters.
Furthermore, recognition of a graphic in the drawing is done in such a manner that the operator appoints graphics one-by-one so that appointment of another graphic for recognition cannot be done until the result of recognition of the preceding graphic is obtained. Moreover, such a conventional drawing recognition system cannot separate image data of a recognized graphical object from a background or a sketch. Therefore, unless all data has been recognized, the background or sketch cannot be combined with the recognized graphic. This restricts the applications of recognized data.